package cxydmmszl.chapter04.t064;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * <li style="color: red;">Prob</li>
 * 汉诺塔问题
 * <li style="color: red;">Desc</li>
 * 给定一个整数 n，代表汉诺塔游戏中从小到大放置 n 个圆盘，假设开始所有圆盘都在左边的柱子上，
 * 那么用最优的办法把所有圆盘都移动到右边的柱子上的过程，就称为最优移动轨迹。
 * 给定一个整型数组 arr, 其中只含有 1、2 和 3,代表所有圆盘目前的状态，1代表左柱，2代表中柱，3代表右柱，
 * a[i] 的值代表第 i+1 个圆盘的位置（a[i]下标从0开始）。
 * 比如，arr=[3,3,2,1], 代表第 1 个圆盘在右柱上、第 2 个圆盘在右柱上、
 * 第 3 个圆盘在中柱上、第 4 个圆盘在左柱上。
 * 如果 arr 代表的状态是最优移动轨迹过程中出现的状态，
 * 输出 arr 这种状态是最优移动轨迹中的第几个状态（由于答案可能较大，请输出对 10^9+7 取模后的答案）。
 * 如果 arr 代表的状态不是最优移动轨迹过程中出现的状态，则输出-1。<br/><br/>
 * 输入描述：<br/>
 * 输入包括两行，第一行一个整数 n(1≤n≤2∗10^6)，表示圆盘的个数，
 * 第二行 n 个正整数，且均为 1 或 2 或 3，第 i 个整数表示第 i 个圆盘位置。<br/><br/>
 * 输出描述：<br/>
 * 输出一个整数，表示这种状态是第几个最优移动状态（输出对 10^9+7 取模后的答案），无解输出 -1。
 * <li style="color: red;">Link</li> CD30
 *
 * @author habitplus
 * @since 2021-09-03 17:21
 */
public class Main {

    private static final int MOD = 1000000007;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        int[] arr = new int[n];
        String[] ss = bf.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(ss[i]);
        }
        bf.close();

        int ans = step(arr);
        System.out.println(ans);
    }

    public static void hanoi(int n) {
        if (n > 0) {
            hanoi(n, "left", "mid", "right");
        }
    }

    // 将前 n 个 盘子从 from，借助 mid，移到 to
    public static void hanoi(int n, String from, String mid, String to) {
        if (n == 1) {
            System.out.println("move from " + from + " to " + to);
        } else {
            hanoi(n - 1, from, to, mid);
            hanoi(1, from, mid, to);
            hanoi(n - 1, mid, from, to);
        }
    }

    public static int step(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }

        int from = 1;
        int mid = 2;
        int to = 3;
        int i = arr.length - 1;
        int res = 0;
        int tmp = 0;

        while (i >= 0) {
            if (arr[i] != from && arr[i] != to) {
                return -1;
            }
            if (arr[i] == to) {
                res = (res + (int)((1L << i) % MOD)) % MOD;
                tmp = from;
                from = mid;
            } else {
                tmp = to;
                to = mid;
            }
            mid = tmp;
            i--;
        }
        return res;
    }
}
